#include <iostream>
#include<string>
#include <map>
#include <set>
#include<stack>
#include<queue>
#include <vector>
#include <memory>
using namespace std;

int n1 = 1;
int n2 = 1;
//NFA
class infixToPostfix {
public:
    infixToPostfix(const string& infix_expression) {
        infix = infix_expression;
        postfix = "";
        isp = { {'+', 3}, {'|', 5}, {'*', 7},  {'(', 1}, {')', 8}, {'#', 0} };
        icp = { {'+', 2}, {'|', 4}, {'*', 6}, {'(', 8}, {')', 1}, {'#', 0} };
    }
    int is_letter(char check) {
        if (check >= 'a' && check <= 'z' || check >= 'A' && check <= 'Z')
            return true;
        return false;
    }
    int ispFunc(char c) {
        int priority = isp.count(c) ? isp[c] : -1;
        if (priority == -1) {
            cerr << "error: 出现未知符号！" << endl;
            exit(1);  // 异常退出
        }
        return priority;
    }
    int icpFunc(char c) {
        int priority = icp.count(c) ? icp[c] : -1;
        if (priority == -1) {
            cerr << "error: 出现未知符号！" << endl;
            exit(1);  // 异常退出
        }
        return priority;
    }
    void inToPost() {
        string infixWithHash = infix + "#";
        stack<char> stack;
        int loc = 0;
        while (!stack.empty() || loc < infixWithHash.size()) {
            if (is_letter(infixWithHash[loc])) {
                postfix += infixWithHash[loc];
                loc++;
            }
            else {
                char c1 = (stack.empty()) ? '#' : stack.top();
                char c2 = infixWithHash[loc];
                if (ispFunc(c1) < icpFunc(c2)) { // 栈顶操作符优先级低于当前字符，将当前字符入栈
                    stack.push(c2);
                    loc++;
                }
                else if (ispFunc(c1) > icpFunc(c2)) {  // 栈顶操作符优先级高于当前字符，将栈顶操作符出栈并添加到后缀表达式
                    postfix += c1;
                    stack.pop();
                }
                else {
                    if (c1 == '#' && c2 == '#') { // 遇到两个 #，表达式结束
                        break;
                    }
                    stack.pop(); //其中右括号遇到左括号时会抵消，左括号出栈，右括号不入栈
                    loc++;
                }
            }
        }
    }
    string getResult() {
        postfix = ""; // 清空结果
        inToPost();
        return postfix;
    }

private:
    string infix;
    string postfix;
    map<char, int> isp;
    map<char, int> icp;
};

class NFAState {
public:
    map<char, set<NFAState*>> transitions; // 转换图
    bool isFinal;
    string id;
    NFAState()
    {
        isFinal = false;
        id = "nfa." + to_string(n1);
        n1++;
    }

    bool operator<(const NFAState& other) const {
        return id < other.id;
    }
};

class NFA {
public:
    NFAState* startState;
    NFAState* acceptState;

    NFA() {
        startState = new NFAState();
        acceptState = new NFAState();
        acceptState->isFinal = true;
    }

    ~NFA() {
        clearStates(startState);
    }

    void clearStates(NFAState* state) {
        state->transitions.clear();
        delete state;
    }
};

int is_letter(char check) {
    if (check >= 'a' && check <= 'z' || check >= 'A' && check <= 'Z')
        return true;
    return false;
}

string add_join_symbol(string add_string)
{
    int length = add_string.size();
    int return_string_length = 0;
    char* return_string = new char[2 * length + 2];//最多是两倍
    char first, second;
    for (int i = 0; i < length - 1; i++)
    {
        first = add_string.at(i);
        second = add_string.at(i + 1);
        return_string[return_string_length++] = first;
        //要加的可能性如ab 、 *b 、 a( 、 )b 等情况
        //若第二个是字母、第一个不是'('、'|'都要添加
        if (first != '(' && first != '|' && is_letter(second))
        {
            return_string[return_string_length++] = '+';
        }
        //若第二个是'(',第一个不是'|'、'(',也要加
        else if (second == '(' && first != '|' && first != '(')
        {
            return_string[return_string_length++] = '+';
        }
    }
    //将最后一个字符写入second
    return_string[return_string_length++] = second;
    return_string[return_string_length] = '\0';
    string STRING(return_string);
    cout << "加'+'后的表达式：" << STRING << endl;
    return STRING;
}

NFA* createNFA(char c) {
    NFA* nfa = new NFA();
    nfa->startState->transitions[c].insert(nfa->acceptState);
    return nfa;
}

NFA* concateNFA(NFA* nfa1, NFA* nfa2) {
    nfa1->acceptState->isFinal = false; // 连接前面的 NFA 的接受状态
    nfa1->acceptState->transitions['#'].insert(nfa2->startState); // # 转换
    nfa1->acceptState = nfa2->acceptState; // 更新接受状态
    return nfa1;
}

NFA* unionNFA(NFA* nfa1, NFA* nfa2) {
    NFA* nfa = new NFA();
    nfa->startState->transitions['#'].insert(nfa1->startState);
    nfa->startState->transitions['#'].insert(nfa2->startState);
    nfa1->acceptState->transitions['#'].insert(nfa->acceptState);
    nfa2->acceptState->transitions['#'].insert(nfa->acceptState);
    return nfa;
}

NFA* starNFA(NFA* nfa) {
    NFA* closureNFA = new NFA();
    closureNFA->startState->transitions['#'].insert(nfa->startState);
    closureNFA->startState->transitions['#'].insert(closureNFA->acceptState);
    nfa->acceptState->transitions['#'].insert(nfa->startState);
    nfa->acceptState->transitions['#'].insert(closureNFA->acceptState);
    return closureNFA;
}

void input(string& RE)
{
    string a;
    cout << "请输入正则表达式：  （操作符：() * |;字符集：a~z A~Z）" << endl;
    cin >> a;
    int n = a.length();
    for (int i = 0; i < n; i++)
    {
        if (a[i] != ' ')
        {
            RE = RE + a[i];
        }
    }
    cout << "正规表达式是：" << RE << endl;
    if (RE.size() <= 1)
    {
        return;
    }
    RE = add_join_symbol(RE);
    infixToPostfix Solution(RE);
    RE = Solution.getResult();
    cout << RE << endl;
}

NFA* trans(const string& s) {
    stack<NFA*> nfaStack;
    char c;
    for (int i = 0; i < s.size(); i++) {
        c = s[i];
        if (isalnum(c)) {
            nfaStack.push(createNFA(c));
        }
        else if (c == '|') {
            NFA* nfa2 = nfaStack.top(); nfaStack.pop();
            NFA* nfa1 = nfaStack.top(); nfaStack.pop();
            nfaStack.push(unionNFA(nfa1, nfa2));
        }
        else if (c == '*') {
            NFA* nfa = nfaStack.top(); nfaStack.pop();
            nfaStack.push(starNFA(nfa));
        }
        else if (c == '+')
        {
            NFA* nfa2 = nfaStack.top(); nfaStack.pop();
            NFA* nfa1 = nfaStack.top(); nfaStack.pop();
            nfaStack.push(concateNFA(nfa1, nfa2));
        }
    }
    return nfaStack.top();
}

void showHelper(NFAState* state, set<NFAState*>& visited) {
    if (visited.find(state) != visited.end()) {
        return; // 已经访问过，避免无限循环
    }
    visited.insert(state); // 标记为已访问
    // 显示所有转换
    for (const auto& pair : state->transitions) {
        char symbol = pair.first;
        const set<NFAState*>& nextStates = pair.second;
        for (NFAState* nextState : nextStates) {
            cout << state->id << "->" << symbol << " ->" << nextState->id << endl;
        }
    }

    // 递归访问所有下一个状态
    for (const auto& pair : state->transitions) {
        for (NFAState* nextState : pair.second) {
            showHelper(nextState, visited);
        }
    }
}

void show(NFA* finalNFA) {
    set<NFAState*> visited; // 记录已访问的状态
    cout << "NFA:" << endl;
    cout << "起始点编号:" << finalNFA->startState->id << endl;
    cout << "终止点编号:" << finalNFA->acceptState->id << endl;
    showHelper(finalNFA->startState, visited); // 从起始状态开始展示
    cout << endl;
}

//DFA
class DFAState {
public:
    set<NFAState*> nfaStates; // 包含的 NFA 状态
    map<char, DFAState*> map;
    bool isFinal;
    string id;

    DFAState()
    {
        isFinal = false;
        id = "dfa." + to_string(n2);
        n2++;
    }
};

class DFA {
public:
    DFAState* startState;
    set<DFAState*> states;

    DFA(DFAState* start) : startState(start) {
        states.insert(start);
    }

    void addState(DFAState* state) {
        states.insert(state);
    }
};

set<NFAState*> epsilonClosure(NFAState* state) {
    set<NFAState*> closure;
    queue<NFAState*> q;
    q.push(state);

    while (!q.empty()) {
        NFAState* current = q.front();
        q.pop();
        if (closure.insert(current).second) {
            for (auto& next : current->transitions['#']) {
                q.push(next);
            }
        }
    }
    return closure;
}

bool check(set<NFAState*> setnfa1, set<NFAState*>setnfa2)
{
    return setnfa1 == setnfa2;
}

DFA* convertNFAtoDFA(NFA* nfa) {
    DFAState* dfaStart = new DFAState();
    dfaStart->nfaStates = epsilonClosure(nfa->startState);
    DFA* dfa = new DFA(dfaStart);
    set<DFAState*> visited;
    queue<DFAState*> dfaStatesQueue;
    dfaStatesQueue.push(dfaStart);
    visited.insert(dfaStart);

    while (!dfaStatesQueue.empty()) {
        DFAState* currentDFAState = dfaStatesQueue.front();
        dfaStatesQueue.pop();
        visited.insert(currentDFAState);
        map<char, set<NFAState*>> transitionMap;

        // 为当前 DFA 状态计算所有转移
        for (auto nfaState : currentDFAState->nfaStates) {
            for (auto& transition : nfaState->transitions) {
                char input = transition.first;
                for (auto nextState : transition.second) {
                    transitionMap[input].insert(nextState);
                }
            }
        }

        // 为 DFA 状态创建新的状态
        for (auto& key : transitionMap) {
            set<NFAState*> nextNFAStates = key.second;
            int nofind = 1;
            for (auto& k : visited)
            {
                if (check(k->nfaStates, nextNFAStates))
                {
                    currentDFAState->map[key.first] = k;
                    nofind = 0;
                    break;
                }
            }
            if (nofind)
            {
                DFAState* newDFAState = new DFAState();
                newDFAState->nfaStates = nextNFAStates;
                // 检查是否为接受状态
                for (auto nfaState : nextNFAStates) {
                    if (nfaState->isFinal) {
                        newDFAState->isFinal = true;
                        break;
                    }
                }
                currentDFAState->map[key.first] = newDFAState;
                dfa->addState(newDFAState);
                dfaStatesQueue.push(newDFAState);
            }
        }
    }
    return dfa;
}

void show(DFA* dfa)
{
    cout << "DFA:" << endl;
    cout << "开始端点编号为：" << dfa->startState->id << endl;
    cout << "终止端点编号为：";
    for (auto& state : dfa->states)
    {
        if (state->isFinal)
        {
            cout << state->id << ",";
        }
    }
    cout << endl;
    for (auto& state : dfa->states)
    {
        for (auto key : state->map)
        {
            cout << state->id << "->" << key.first << " ->" << key.second->id << endl;
        }
    }
    cout << endl;
}

int main() {
    string s;
    input(s);
    NFA* finalNFA = trans(s);
    show(finalNFA);

    DFA* finalDFA = convertNFAtoDFA(finalNFA);
    show(finalDFA);

    delete finalDFA;
    delete finalNFA; // 清理内存
    return 0;
}
